//1.公共节点
//思路1:双指针问题；1，先找到长链表，长链表的长度走x步与短链表长度一致；2.两个指针指向两个链表一起走；

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1=pHead1, *p2=pHead2;
        int len1=0, len2=0;
        //计算两个链表的长度。
        while (p1 != nullptr){
            p1 = p1->next;
            len1++;
        }
        while (p2 != nullptr){
            p2 = p2->next;
            len2++;
        }
 
        //在长链表上先移动一段距离。
        while (len1!=len2){
            if (len1>len2){
                pHead1 = pHead1->next;
                len1--;
            }
            else{
                pHead2 = pHead2->next;
                len2--;
            }
        }
        //双指针同时开始后移。
        while (pHead1 != pHead2){
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return pHead1;
    }
};